Theoretische Informatik 理论信息学

大纲/总结

• 2.Grundbegriffe

  • 2.1 Grammatiken

  • 2.2 Die Chomsky-Hierarchie：

    Typ 0 (Phrasenstruktur), 1 (Kontextsensitive), 2 (Kontextfreie), 3 (Rechtslinear, Regulär)

• 3.Reguläre Sprachen （Typ 3）

  • 3.1 Deterministische endliche Automaten

  • 3.2 Von rechtslinearen Grammatiken zu DFA (und zurück)

  • 3.3 NFAs mit epsilon-Übergängen

  • 3.4 Reguläre Ausdrücke

  • 3.5 Von NFA zu RE als Lösung eines Gleichungssystems：

    推导NFA对应的RE，以及从RE对应的NFA。

  • 3.6 Rechnen mit regulären Ausdrücken：

    一些等价的RE。

  • 3.7 Abschlusseigenschaften regulärer Sprachen：

    regulärer Sprachen的交并集，补集，乘集等都是regulärer的。

  • 3.8 Pumping Lemma：

    Reguläre Sprache的特殊性质，可以用于证明某个Sprache不是regulär的。

  • 3.9 Entscheidungsverfahren：

    以下几个问题的可解性以及复杂度：Wortproblem, Leerheitsproblem, Endlichkeitsproblem, Äquivalenzproblem。

  • 3.10 Minimierung endlicher Automaten：

    每个DFA都能（利用等价类）化简到minimal。

• 4.Kontextfreie Sprachen （Typ 2）

  • 4.1 Kontextfreie Grammatiken

    Syntaxbaum，复习定义，新缩写：CFG （Kontextfreie Grammatik），CFL （Kontextfreie Sprache）。

  • 4.2 Induktive Definitionen, Syntaxbäume und Ableitungen

    Wort的推导/生成都有一个对应的Syntaxbaum。

  • 4.3 Die Chomsky-Normalform

    epsilon-Produktion，Kettenproduktion，（如何构造）Chomsky-Normalform，Greibach-Normalform。

  • 4.4 Das Pumping-Lemma für kontextfreie Sprachen：

    和之前的类似，适合用于证明某个Sprache不是kontextfrei的。

  • 4.5 Abschlusseigenschaften：

    Vereinigung，Konkatenation，Stern，Spiegelung后的都还是kontextfrei，但是交集，补集不一定是了。

  • 4.6 Algorithmen für kontextfreie Grammatiken

  • 4.7 Der Cocke-Younger-Kasami-Algorithmus

    CYK算法，用于验证一个单词是否属于一个文法（Grammatik）。

  • 4.8 Kellerautomaten

    Pushdown Automaton （PDA）

  • 4.9 Äquivalenz von PDAs und CFGs

  • 4.10 Deterministische Kellerautomaten

  • 4.11 Tabellarischer Überblick

• 5. Berechenbarkeit, Entscheidbarkeit

  • 5.1 Der Begriff der Berechenbarkeit

    Berechenbarkeit，Turingmaschine

  • 5.2 Unentscheidbarkeit des Halteproblems

  • 5.3 Semi-Entscheidbarkeit

  • 5.4 Die Sätze von Rice und Shapiro

  • 5.5 Das Postsche Korrespondenzproblem

  • 5.6 Unentscheidbare CFG-Probleme

• 6. Komplexitätstheorie

  • 6.1 Die Komplexitätsklasse P
  • 6.2 Die Komplexitätsklasse NP
  • 6.3 NP-Vollständigkeit
  • 6.4 Weitere NP-vollständige Probleme
  • 6.5 Die Unvollständigkeit der Arithmetik
  • 6.6 Die Entscheidbarkeit der Presburger Arithmetik

需要掌握的算法：

• 第三章：

  • Grammatik转NFA（Satz 3.9；H 3.1，T 2.2）

  • NFA转DFA （Satz 3.10）

    • Potenzmengenkonstruktion

  • DFA转Grammatik （Satz 3.13）

  • epsilon-NFA转NFA（Lemma 3.16）

  • NFA转regulär Ausdruck

    • 画图（T 4.1）
    • 高斯消元/解方程/Ardens Lemma（T 4.2，H 4.1）

  • Regulär Ausdruck转epsilon-NFA（T 3.3，H 3.4）

  • DFA Minimierung（Tabelle）（T 5.3 a)，H 5.3）
  • 构造regulär Ausdruck对应的Minimalautomat

• 第四章：

  • 构造CFG的Chomsky-Normalform（T 7.1，T 7.4，H 7.1）
  • 消除Grammatik的unnützliche Symbole（T 8.1，H 8.1）
  • CYK（CYK Tabelle，用于验证一个单词是否属于一个文法（Grammatik））（T 8.2 b)，T 8.5，H 8.2.）
  • Grammatik转PDA（Satz 4.53，T 9.3）
  • CFG转PDA
  • PDA转CFG

不同Type的语言以及对应的自动机：

基本概念

注意，这里的形式语言（(formale) Sprache）$L$并没有要求必须包含$\varepsilon$。

来看一下简单的（形式）语言 （(formale) Sprache）的例子：

• 杜登（Duden）词典中所有单词的集合

• $L_1 = \{ \varepsilon, ab, abab, ababab, \dots \} = \{ (ab)^n \mid n \in \mathbb{N} \}$

  （$\Sigma_1 = \{a, b\}$）

• $L_2 = \{ \varepsilon, ab, aabb, abab, abba, baab, baba, bbaa, \dots \} = \{ w \in \{a,b\}^* \mid w\ \text{中包含相同数量的}\ a\ \text{和}\ b\ \text{字符} \}$

  （$\Sigma_2 = \{a, b\}$）

• $L_3 = \{0, 1, 100, 1001, 10000, \dots\} = \{ w \in \{0,1\}^* \mid w\ \text{是一个二进制编码的平方数} \}$

  （$\Sigma_3 = \{0,1\}$）

• $\emptyset$

• $\{\varepsilon\}$

反例：

• $\varepsilon$ 或 $ab$ 不是语言，因为它们不是集合。

注意，因为$A^0 = \{ \varepsilon \}$，所以对于所有 $A$ 都有：$\varepsilon \in A^$，并且 $\emptyset^ = \{ \varepsilon \}$。

证明：Trivial。$\square$

证明：Trivial。$\square$

但是注意，$A(B \cap C) \neq AB \cap AC$不一定一直成立。

反例：$A=\{a,ab\}, B=\{b\}, C =\{\varepsilon\}$：

$$A(B\cap C) = A \emptyset = \emptyset$$ $$AB \cap AC = \{ab,abb\} \cap \{a,ab\} = \{ab\} \neq \emptyset$$

最根本的原因是可能存在$u’v’= u’’v’’ \in AB \cap AC$并且$u’ \neq u’’, v’ \neq v’’$。这就导致不能从$uv \in AB \cap AC$推出存在$u \in A, v \in B \cap C$。

证明：Trivial。$\square$

文法（Grammatiken）

为了方便，我们一般用：

• $\alpha \to \beta$ 指代 $(\alpha, \beta) \in P$；
• $\alpha \to \beta_1|\cdots |\beta_n$ 指代 $\alpha \to \beta_1, …, \alpha \to \beta_n$

注意，定义里的$\alpha_1, \alpha_2$可以是$\varepsilon$，也可以是其他单词的Konkatenation。所以在一个大的Konkatenation里，对于其中一个存在Produktion，那么对整个Konkatenation都存在一个推导。

例子：

• $V = \{ \langle \text{Expr} \rangle, \langle \text{Term} \rangle, \langle \text{Factor} \rangle \}$

• $\Sigma = \{ a, b, c, +, *, (, ) \}$

• $S = \langle \text{Expr} \rangle$

• $P$：

  $$\begin{align} \langle \text{Expr} \rangle &\to \langle \text{Term} \rangle \\ \langle \text{Expr} \rangle &\to \langle \text{Expr} \rangle + \langle \text{Term} \rangle \\ \langle \text{Term} \rangle &\to \langle \text{Factor} \rangle \\ \langle \text{Term} \rangle &\to \langle \text{Term} \rangle * \langle \text{Factor} \rangle \\ \langle \text{Factor} \rangle &\to a\ \mid\ b\ \mid\ c \\ \langle \text{Factor} \rangle &\to (\langle \text{Expr} \rangle) \end{align}$$

该如何从$\langle \text{Expr} \rangle$推导出$a * (b + c)$呢？

$$\begin{align*} \langle \text{Expr} \rangle &\xrightarrow{1} \langle \text{Term} \rangle \xrightarrow{4} \langle \text{Term} \rangle * \langle \text{Factor} \rangle \xrightarrow{3} \langle \text{Factor} \rangle * \langle \text{Factor} \rangle \\ &\xrightarrow{5} a * \langle \text{Factor} \rangle \xrightarrow{6} a * (\langle \text{Expr} \rangle) \xrightarrow{2} a * (\langle \text{Expr} \rangle + \langle \text{Term} \rangle) \\ &\xrightarrow{1} a * (\langle \text{Term} \rangle + \langle \text{Term} \rangle) \xrightarrow{3} a * (\langle \text{Factor} \rangle + \langle \text{Term} \rangle) \xrightarrow{3} a * (\langle \text{Factor} \rangle + \langle \text{Factor} \rangle)\\ &\xrightarrow{5} a * (b + \langle \text{Factor} \rangle) \xrightarrow{5} a * (b+ c) \end{align*}$$

一共需要11步。

例子：

这两个语法：

$$\begin{align*} G_1: \quad S &\to abcS \mid \epsilon \\ ba &\to ab \\ cb &\to bc \\ ca &\to ac \end{align*}$$ $$\begin{align*} G_1: \quad S &\to aBSc \mid \epsilon \\ Ba &\to aB \\ Bb &\to bB \\ Bc &\to bc \end{align*}$$

哪个可以生成$M = \{ a^n b^n c^n \mid n \geq 0 \}$呢？

首先，有$M \subseteq L(G_1)$，因为$S \to abcS \to abcabcS \to abcabc \to abacbc \to aabcbc \to aabbcc$。

只不过$L(G_1) \neq M$，因为$S \to abcS \to abcabcS \to abcabc$。

而$L(G_2) = M$，因为：

$$S \to aBSc \to aBaBcc \to aBaBcc \to aaBBcc \to aaBbcc \to aabBcc \to aabbcc.$$

不难注意到有：

$$L(G) = \{ w \in \Sigma^* | S \to_G^* w \}.$$

例子：在前面的例子我们已经看到了$\langle \text{Expr} \rangle$推导出$a * (b + c)$需要11步，所以有

$$\langle \text{Expr} \rangle \to_G^{11} a * (b + c)$$

并因此有

$$\langle \text{Expr} \rangle \to_G^* a * (b + c)$$

和

$$\langle \text{Expr} \rangle \to_G^+ a * (b + c)$$

乔姆斯基体系（Chomsky Hierarchie）

显然有：

$$\text{Typ 3} \subseteq \text{Typ 2} \subseteq \text{Typ 1} \subseteq \text{Typ 0}$$

Wortproblem：

Gegeben: 一个文法 $G$ 和一个单词 $w \in \Sigma^*$，
Frage：$w$ 是否属于 $L(G)$？

不同Type的语言以及对应的自动机：

正规语言（Reguläre Sprachen）

等价关系：

Deterministische endliche Automaten

名字里的deterministisch是指：对于每一个状态（Zustand）以及一个Übergang只对应一个状态（Zustand）。

可以这样理解$\hat{\delta}$：第一个参数是起始状况（Zustand），然后第二个参数的一连串的路径（或者说是操作），会依次触发/经过。

所以

$$L(M) := \{ w \in \Sigma^* \mid \hat{\delta}(q_0, w) \in F \},$$

里的元素翻译一下就是：所有从起点到终点的路径/操作序列。

所有endliche Automaten都可以用gerichtete und makierte Zustandsgraph表示出来，其中

• 点（Knoten）代表Zustände；
• 线（Kanten）表示Übergänge $p \xrightarrow{a} q$ ，即$\delta(p,a)= q$；
• Anfangszustand 会被用一个箭头（Pfeil）标记出来；
• Endzustände 会被用doppelte Kreise标记出来。

例子：

• $Q = \{0,1,2\}$
• $\Sigma = \{a,b\}$

不难注意到，在这里例子里，所有可以被akzeptiert的Wort都一定包含ab。（相当于必经之路）

同样，所有包含ab的Wort也一定会被akzeptiert。

例子：

我们用#w表示w的二进制。（比如说#100=4）

不难发现，DFA akzeptiert $w \in \{0,1\}^*$当且仅当#w是偶数。

证明：

假设$w \neq \varepsilon$，可以通过

$$\hat{\delta}(0, w0) = \delta(\hat{\delta}(0, w), 0) = 0 \in F$$ $$\hat{\delta}(0, w1) = \delta(\hat{\delta}(0, w), 1) = 1 \notin F$$

可以得到

$$w0 \in L(A), w1 \notin L(A)$$

即$w \in L(A) \Leftrightarrow w\text{为偶数}$。（也就是二进制的最低位等于0）

如果$w = \varepsilon$，有$\hat{\delta}(0, \varepsilon) = 0$，所以$\varepsilon \in L(A)$。（注意 #$\varepsilon = 0$）$\square$

Von rechtslinearen Grammatiken zu DFA (und zurück)

Rechtslineare Grammatik（即Typ3）指的是所有Produktion都长这样：$A \to a$ 或者$A \to aB$。

注意，在DFA里，每一个状态（Zustand）以及一个Übergang只对应一个状态（Zustand）。而在NFA里，一个状态（Zustand）以及一个Übergang可以对应多个状态。

例子：

每一个点可能会拥有多条相同名字的边，所以结果是不确定的。（nichtdeterministisch ）

当我们输入$0111$，可能会得到多个Zustandsfolgen：

$$p,p,p,p,p, \ \ \ p,p,p,p,q \ \ \ p,p,p,q,r$$

和之前类似，我们可以在$\delta$的基础上定义

$$\begin{align*} \bar{\delta}: \mathcal{P}(Q) \times \Sigma &\to \mathcal{P}(Q) \\ \bar{\delta}(S,a) :&= \bigcup_{q \in S} \delta(q, a) \end{align*}$$

并在这个基础上像之前一样inductive定义

$$\hat{\bar{\delta}} : \mathcal{P}(Q) \times \Sigma^* \rightarrow \mathcal{P}(Q)$$

而$\hat{\delta}(S, w)$ 可以理解成是Menge aller Zustände, die sich von einem Zustand in $S$ aus mit $w$ erreichen lassen.

例子：

$$\begin{aligned} \hat{\bar{\delta}}(\{p,q\},10) &= \hat{\bar{\delta}}(\bar{\delta}(\{p, q\}, 1), 0) \\ &= \hat{\bar{\delta}}(\delta(p, 1) \cup \delta(q, 1), 0) \\ &= \hat{\bar{\delta}}(\{p, q, r\}, 0) \\ &= \bar{\delta}(\{p, q, r\}, 0) \\ &= \delta(p, 0) \cup \delta(q, 0) \cup \delta(r, 0) \\ &= \{p\} \cup \{r\} \cup \emptyset \\ &= \{p, r\} \end{aligned}$$

也就是说从$p,q$出发，进行一遍$10$的操作，最后一定会落在$p,r$。

注意，在DFA定义的akzeptierte Sprache里，是

$$L(M) := \{ w \in \Sigma^* \mid \hat{\delta}(q_0, w) \in F \},$$

而在这里，由于$\hat{\delta}(q_0, w)$ 是几个集合，所以我们要求的是它和$F$的交集不为空，也就是说只要存在到达的可能性那就会被akzeptiert。

为了方便，我们后续一般还是用$\delta$ 指代$\bar{\delta}$ ， $\hat{\delta}$ 指代$\hat{\bar{\delta}}$ 。

主要的构造（证明）思路就是将Grammatik里的Variablen （V）构造成NFA的Zustände（Q），然后将Grammatik的Produktion构造成NFA里的Übergänge。

我们来看一下针对下面这个比较allgemein的例子的具体构造。

例子：

$$\begin{aligned} S &\rightarrow aX \mid aY \\ X &\rightarrow aX \mid bY \mid a \\ Y &\rightarrow aS \mid bX \mid aY \mid b \end{aligned}$$

证明（构造）：

Sei $G = (V, \Sigma, P, S)$ eine rechtslineare Grammatik ohne die Produktion $S \rightarrow \varepsilon$.
Definiere den NFA $A = (Q, \Sigma, \delta, q_0, F)$ mit:

• $Q = V \cup \{q_f\}$ (wobei $q_f \notin V$)
• $Y \in \delta(X, a)$ gdw $(X \rightarrow aY) \in P$
• $q_f \in \delta(X, a)$ gdw $(X \rightarrow a) \in P$
• $q_0 = S$
• $F = \{q_f\}$

Es gilt: $a_1 \ldots a_n \in L(G)$

– gdw es existieren Variablen $X_1, \ldots, X_{n-1}$

$$S \rightarrow a_1X_1 \rightarrow_G a_1a_2X_2 \rightarrow_G \cdots \rightarrow_G a_1 \ldots a_{n-1}X_{n-1} \rightarrow_G a_1 \ldots a_n$$

– gdw es existieren Zustände $X_1, \ldots, X_{n-1}$

$$\delta(S, a_1) \ni X_1,\quad \delta(X_1, a_2) \ni X_2,\quad \ldots,\quad \delta(X_{n-1}, a_n) \ni q_F$$

– gdw $a_1 \ldots a_n \in L(A)$

. $\square$

假设这个Grammatik还包含了$S \to \varepsilon$，那么需要将$F$构造成$F= \{S, q_f\}$。

证明：

Sei $N = (Q, \Sigma, \delta, q_0, F)$ ein NFA.
Definiere den DFA $M = (\mathcal{P}(Q), \Sigma, \bar{\delta}, \{q_0\}, F_M)$:

$$F_M := \{ S \subseteq Q \mid S \cap F \neq \emptyset \}$$

Dann gilt:

$$\begin{aligned} w \in L(N) &\Leftrightarrow \hat{\bar{\delta}}(\{q_0\}, w) \cap F \neq \emptyset &\text{Def.} \\ &\Leftrightarrow \hat{\bar{\delta}}(\{q_0\}, w) \in F_M &\text{Def.} \\ &\Leftrightarrow w \in L(M) &\text{Def.} \end{aligned}$$

. $\square$

这种构造叫做 Potenzmengenkonstruktion 或者 Teilmengenkonstruktion。

注意，按照这个构造，如果NFA里有n个Zustände， 那对应的DFA里会有$2^n$个Zustände。很多当然是可以避免这个规格的，但是有些时候并避免不了。在这个Corollary之后我们会看一个避免不了的例子。

例子：

$$L_k := \{ w \in \{0,1\}^* \mid \text{das $k$-letzte Bit von } w \text{ ist } 1 \}$$

（注意，这里是倒数第$k$位为1，不是正数。）

Ein NFA für diese Sprache:

证明：

我们需要做的是证明 für alle $w_1, w_2 \in \{0, 1\}^k$:

$$w_1 \ne w_2 \Rightarrow \hat{\delta}(q_0, w_1) \ne \hat{\delta}(q_0, w_2)$$

证明了这个之后，由于$\{0, 1\}^k$里有$2^k$个元素，那么任意一个DFA里也至少会有$2^k$个Zusände，因为对于所有的$w \in \{0, 1\}^k$，$\hat{\delta}(q_0, w)$都是$M$里的一个Zustand。

那么我们现在开始证明这个结论，用反证法：

Annahme: Es gibt $w_1, w_2 \in \{0, 1\}^k$ mit $w_1 \ne w_2$, aber $\hat{\delta}(q_0, w_1) = \hat{\delta}(q_0, w_2)$.

Sei $w_1 = wa_i \ldots a_k$ und $w_2 = wb_i \ldots b_k$ mit $a_i \ne b_i$ （$i$表示的是$w_1,w_2$第一个不相等的位。而前面相同的部分我们就简单记作$w$。）
o.E. sei $a_i = 1$, $b_i = 0$.

Es gilt einerseits:

$$\begin{aligned} w_1 0^{i-1} &= wa_i \ldots a_k 0^{i-1} \in L_k \\ w_2 0^{i-1} &= wb_i \ldots b_k 0^{i-1} \notin L_k \end{aligned}$$

（在$w_1,w_2$后面加上$i-1$个0，这样一来第一个的倒数第$k$位就是1，第二个的倒数第$k$位是0。）

Aber es gilt auch:

$$\begin{aligned} \hat{\delta}(q_0, w_1 0^{i-1}) &= \hat{\delta}(\hat{\delta}(q_0, w_1), 0^{i-1}) \\ &= \hat{\delta}(\hat{\delta}(q_0, w_2), 0^{i-1}) \quad \text{nach der Annahme}\\ &= \hat{\delta}(q_0, w_2 0^{i-1}) \end{aligned}$$

但是根据$L(M)$的定义：

$$L(M) := \{ w \in \Sigma^* \mid \hat{\delta}(q_0, w) \in F \},$$

不可能存在$a,b$满足$\hat{\delta}(q_0, a) = \hat{\delta}(q_0, b)$，但是一个在$L(M)$，一个不在。

所以说得到一个Wiederspruch. $\square$

证明：

Sei $M = (Q, \Sigma, \delta, q_0, F)$.
Die Grammatik $G = (V, T, P, S)$ mit:

• $V = Q$, $T = \Sigma$, $S = q_0$
• $(q_1 \rightarrow aq_2) \in P$ gdw $\delta(q_1, a) = q_2$
• $(q_1 \rightarrow a) \in P$ gdw $\delta(q_1, a) \in F$
• $(q_0 \rightarrow \varepsilon) \in P$ gdw $q_0 \in F$

ist von Typ 3 und erfüllt $L(M) = L(G)$.$\square$

NFAs mit $\epsilon$-Übergängen

注意，这里的$\epsilon$和之前用的$\varepsilon$是不一样的东西。

$\epsilon$ ist ein einzelnes Symbol, $\varepsilon$ ist das leere Wort.

例子：

这个$\varepsilon$-NFA可以接受$\varepsilon,00,11,…$，但不能接受$101,…$。

也就是说，这个Automat虽然读取的是$11$，但它可以先（“免费”）跳到$q_1$，然后再进行2次$1$的操作。

证明：

Sei $N = (Q, \Sigma, \delta, q_0, F)$ ein $\epsilon$-NFA.
Wir definieren den NFA
$N’ = (Q, \Sigma, \delta’, q_0, F’)$ mit folgenden Definitionen für $\delta’$ und $F’$:

• $\delta’ : Q \times \Sigma \rightarrow \mathcal{P}(Q)$

  $$\delta'(q, a) := \bigcup_{i \geq 0, j \geq 0} \hat{\delta}(\{q\}, \epsilon^i a \epsilon^j)$$

• Falls $N$ das leere Wort $\varepsilon$ akzeptiert, also falls

  $$\exists i \geq 0 : \hat{\delta}(\{q_0\}, \epsilon^i) \cap F \neq \emptyset$$

  dann setze $F’ := F \cup \{q_0\}$, sonst setze $F’ := F$.$\square$

例子：

Reguläre Ausdrücke 正则表达式

Berechenbarkeit, Entscheidbarkeit

Begriffe

图灵机 （Turing Maschine）

可以这样理解：机器会（依靠一个探头 read/write head）读取一条Band上的内容，然后根据当前位置进行以下操作：

• 调整当前位置
• 改写Band当前位置的值
• 调整探头位置（左/右/不动）